Информация об изменениях

Сообщение F# и уменьшение сложности алгоритма поиска пересечений всех от 17.02.2020 16:19

Изменено 17.02.2020 16:23 zverjuga

Старый текст
Новый текст
Разница

F# и уменьшение сложности алгоритма поиска пересечений всех

есть следующая задачка. найти все возможные пересечения в списке, которые содержит в себе "дороги", то есть объекты, состоящие из координат. нарисовал координатную сетку 8х8 и на ней 4 горизонтальные и 3 вертикальные линии. в коде это выглядит как то так

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# и уменьшение сложности алгоритма поиска пересечений всех

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];
                    ]

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