Сообщение F# и уменьшение сложности алгоритма поиска пересечений всех от 17.02.2020 16:19
Изменено 17.02.2020 16:25 zverjuga
F# и уменьшение сложности алгоритма поиска пересечений всех
есть следующая задачка. найти все возможные пересечения в списке, которые содержит в себе "дороги", то есть объекты, состоящие из координат. нарисовал координатную сетку 8х8 и на ней 4 горизонтальные и 3 вертикальные линии. в коде это выглядит как то так
далее вызываю соответствующий метод для получения множества всех возможных пересечений (должно быть 12) пересечений
код алгоритма привожу ниже (весь тип не привожу, только то, что нужно)
код работает корректно, но результаты удваиваются, то есть итоговый список содержал дважды правильные ответы. проблема фиксится путем добавления
поскрипев мозгами, прихожу к выводу, что двойные результаты обусловлены тем, что алгоритм дважды проходит один и тот же путь (сначала он горизонтальную линии пересекает с вертикальной, а потом вертикальную с горизонтальной). думаю, что по идее проблему также можно пофиксить и мемоизацией, но:
1. оттого сложность алгоритма все равно не уменьшится. все равно сначала нужно получить результат, а потом смотреть мемоизацию
2. опять таки не совсем понятно, как эту мемоизацию в данном случае использовать и будет ли она работать лучше или быстрее дистинкта.
отсюда возникает вопрос, как можно все таки избежать мемоизации и одновременно не просчитывать один и тот же путь дважды?
ну и в принципе? как можно сделать алгоритм менее сложным.
спасибо
let rh1 =
road "rh1" [ // дорога содержит имя и список точек
point (1., 7., 0.) [BEGIN; COORDINATE]; // точка point (x,y,z) - координата, [] - содержит массив типов точки (не имеет значения в данном случае)
point (3., 7., 0.) [COORDINATE];
point (5., 7., 0.) [COORDINATE];
point (7., 7., 0.) [COORDINATE];
point (8., 7., 0.) [COORDINATE; TRAFFICLIGHT; END];
]
let rh2 =
road "rh2" [
point (1., 5., 0.) [BEGIN; COORDINATE];
point (3., 5., 0.) [COORDINATE];
point (5., 5., 0.) [COORDINATE];
point (7., 5., 0.) [COORDINATE];
point (8., 5., 0.) [COORDINATE; TRAFFICLIGHT; END];
]
let rh3 =
road "rh3" [
point (1., 3., 0.) [BEGIN; COORDINATE];
point (3., 3., 0.) [COORDINATE];
point (5., 3., 0.) [COORDINATE];
point (7., 3., 0.) [COORDINATE];
point (8., 3., 0.) [COORDINATE; TRAFFICLIGHT; END];
]
let rh4 =
road "rh4" [
point (1., 1., 0.) [BEGIN; COORDINATE];
point (3., 1., 0.) [COORDINATE];
point (5., 1., 0.) [COORDINATE];
point (7., 1., 0.) [COORDINATE];
point (8., 1., 0.) [COORDINATE; TRAFFICLIGHT; END];
]
let rv1 =
road "rv1" [
point (3., 8., 0.) [BEGIN; COORDINATE];
point (3., 7., 0.) [COORDINATE];
point (3., 5., 0.) [COORDINATE];
point (3., 3., 0.) [COORDINATE];
point (3., 1., 0.) [COORDINATE];
point (3., 0., 0.) [END; COORDINATE; TRAFFICLIGHT];
]
let rv2 =
road "rv2" [
point (5., 8., 0.) [BEGIN; COORDINATE];
point (5., 7., 0.) [COORDINATE];
point (5., 5., 0.) [COORDINATE];
point (5., 3., 0.) [COORDINATE];
point (5., 1., 0.) [COORDINATE];
point (5., 0., 0.) [END; COORDINATE; TRAFFICLIGHT];
]
let rv3 =
road "rv3" [
point (7., 8., 0.) [BEGIN; COORDINATE];
point (7., 7., 0.) [COORDINATE];
point (7., 5., 0.) [COORDINATE];
point (7., 3., 0.) [COORDINATE];
point (7., 1., 0.) [COORDINATE];
point (7., 0., 0.) [END; COORDINATE; TRAFFICLIGHT];
]далее вызываю соответствующий метод для получения множества всех возможных пересечений (должно быть 12) пересечений
let crossrods = Road.CrossRoads [rh1; rh2; rh3; rh4; rv1; rv2; rv3]
crossrods
|> Seq.iter (fun x -> printfn "position x: %f, y: %f" x.p.x x.p.y)код алгоритма привожу ниже (весь тип не привожу, только то, что нужно)
static member CrossRoads2 r1 r2 =
r1.pl
|> List.filter (fun c1 -> match (c1.p, r2.pl) with
| Includes(_) -> true
| _ -> false
)
static member CrossRoads (roads: Road list) =
let rec inCross r roads res =
match roads with
| h::t when h.n <> r.n ->
let nextRes = Seq.append res (Road.CrossRoads2 r h)
inCross r t nextRes
| _::t ->
inCross r t res
| [] -> res
roads
|> Seq.map (fun x -> inCross x roads Seq.empty)
|> Seq.collect (fun r -> r)
|> Seq.distinct // это фиксит проблему двойного результатакод работает корректно, но результаты удваиваются, то есть итоговый список содержал дважды правильные ответы. проблема фиксится путем добавления
|> Seq.distinctпоскрипев мозгами, прихожу к выводу, что двойные результаты обусловлены тем, что алгоритм дважды проходит один и тот же путь (сначала он горизонтальную линии пересекает с вертикальной, а потом вертикальную с горизонтальной). думаю, что по идее проблему также можно пофиксить и мемоизацией, но:
1. оттого сложность алгоритма все равно не уменьшится. все равно сначала нужно получить результат, а потом смотреть мемоизацию
2. опять таки не совсем понятно, как эту мемоизацию в данном случае использовать и будет ли она работать лучше или быстрее дистинкта.
отсюда возникает вопрос, как можно все таки избежать мемоизации и одновременно не просчитывать один и тот же путь дважды?
ну и в принципе? как можно сделать алгоритм менее сложным.
спасибо
F# и уменьшение сложности алгоритма поиска пересечений всех
есть следующая задачка. найти все возможные пересечения в списке, которые содержит в себе "дороги", то есть объекты, состоящие из координат. нарисовал координатную сетку 8х8 и на ней 4 горизонтальные и 3 вертикальные линии. в коде это выглядит как то так
далее вызываю соответствующий метод для получения множества всех возможных пересечений (должно быть 12) пересечений
код алгоритма привожу ниже (весь тип не привожу, только то, что нужно)
код работает корректно, но результаты удваиваются, то есть итоговый список содержал дважды правильные ответы. проблема фиксится путем добавления
поскрипев мозгами, прихожу к выводу, что двойные результаты обусловлены тем, что алгоритм дважды проходит один и тот же путь (сначала он горизонтальную линии пересекает с вертикальной, а потом вертикальную с горизонтальной). думаю, что по идее проблему также можно пофиксить и мемоизацией, но:
1. оттого сложность алгоритма все равно не уменьшится. все равно сначала нужно получить результат, а потом смотреть мемоизацию
2. опять таки не совсем понятно, как эту мемоизацию в данном случае использовать и будет ли она работать лучше или быстрее дистинкта.
отсюда возникает вопрос, как можно все таки избежать мемоизации и одновременно не просчитывать один и тот же путь дважды?
ну и в принципе? как можно сделать алгоритм менее сложным.
спасибо
let rh1 =
road "rh1" [ // дорога содержит имя и список точек
point (1., 7., 0.) [BEGIN; COORDINATE]; // точка point (x,y,z) - координата, [] - содержит массив типов точки (не имеет значения в данном случае)
point (3., 7., 0.) [COORDINATE];
point (5., 7., 0.) [COORDINATE];
point (7., 7., 0.) [COORDINATE];
point (8., 7., 0.) [COORDINATE; TRAFFICLIGHT; END];
]
let rh2 =
road "rh2" [
point (1., 5., 0.) [BEGIN; COORDINATE];
point (3., 5., 0.) [COORDINATE];
point (5., 5., 0.) [COORDINATE];
point (7., 5., 0.) [COORDINATE];
point (8., 5., 0.) [COORDINATE; TRAFFICLIGHT; END];
]
let rh3 =
road "rh3" [
point (1., 3., 0.) [BEGIN; COORDINATE];
point (3., 3., 0.) [COORDINATE];
point (5., 3., 0.) [COORDINATE];
point (7., 3., 0.) [COORDINATE];
point (8., 3., 0.) [COORDINATE; TRAFFICLIGHT; END];
]
let rh4 =
road "rh4" [
point (1., 1., 0.) [BEGIN; COORDINATE];
point (3., 1., 0.) [COORDINATE];
point (5., 1., 0.) [COORDINATE];
point (7., 1., 0.) [COORDINATE];
point (8., 1., 0.) [COORDINATE; TRAFFICLIGHT; END];
]
let rv1 =
road "rv1" [
point (3., 8., 0.) [BEGIN; COORDINATE];
point (3., 7., 0.) [COORDINATE];
point (3., 5., 0.) [COORDINATE];
point (3., 3., 0.) [COORDINATE];
point (3., 1., 0.) [COORDINATE];
point (3., 0., 0.) [END; COORDINATE; TRAFFICLIGHT];
]
let rv2 =
road "rv2" [
point (5., 8., 0.) [BEGIN; COORDINATE];
point (5., 7., 0.) [COORDINATE];
point (5., 5., 0.) [COORDINATE];
point (5., 3., 0.) [COORDINATE];
point (5., 1., 0.) [COORDINATE];
point (5., 0., 0.) [END; COORDINATE; TRAFFICLIGHT];
]
let rv3 =
road "rv3" [
point (7., 8., 0.) [BEGIN; COORDINATE];
point (7., 7., 0.) [COORDINATE];
point (7., 5., 0.) [COORDINATE];
point (7., 3., 0.) [COORDINATE];
point (7., 1., 0.) [COORDINATE];
point (7., 0., 0.) [END; COORDINATE; TRAFFICLIGHT];
]далее вызываю соответствующий метод для получения множества всех возможных пересечений (должно быть 12) пересечений
let crossrods = Road.CrossRoads [rh1; rh2; rh3; rh4; rv1; rv2; rv3]
crossrods
|> Seq.iter (fun x -> printfn "position x: %f, y: %f" x.p.x x.p.y)код алгоритма привожу ниже (весь тип не привожу, только то, что нужно)
let (|Includes|DoesntIncludes|) (point, list) =
let tryPoint = List.tryFind (fun c2 ->
if point == c2.p then
true
else
false) list
match tryPoint with
| Some(x) -> Includes x
| _ -> DoesntIncludes
static member CrossRoads2 r1 r2 =
r1.pl
|> List.filter (fun c1 -> match (c1.p, r2.pl) with
| Includes(_) -> true
| _ -> false
)
static member CrossRoads (roads: Road list) =
let rec inCross r roads res =
match roads with
| h::t when h.n <> r.n ->
let nextRes = Seq.append res (Road.CrossRoads2 r h)
inCross r t nextRes
| _::t ->
inCross r t res
| [] -> res
roads
|> Seq.map (fun x -> inCross x roads Seq.empty)
|> Seq.collect (fun r -> r)
|> Seq.distinct // это фиксит проблему двойного результатакод работает корректно, но результаты удваиваются, то есть итоговый список содержал дважды правильные ответы. проблема фиксится путем добавления
|> Seq.distinctпоскрипев мозгами, прихожу к выводу, что двойные результаты обусловлены тем, что алгоритм дважды проходит один и тот же путь (сначала он горизонтальную линии пересекает с вертикальной, а потом вертикальную с горизонтальной). думаю, что по идее проблему также можно пофиксить и мемоизацией, но:
1. оттого сложность алгоритма все равно не уменьшится. все равно сначала нужно получить результат, а потом смотреть мемоизацию
2. опять таки не совсем понятно, как эту мемоизацию в данном случае использовать и будет ли она работать лучше или быстрее дистинкта.
отсюда возникает вопрос, как можно все таки избежать мемоизации и одновременно не просчитывать один и тот же путь дважды?
ну и в принципе? как можно сделать алгоритм менее сложным.
спасибо