Всички възможни пътища

В момента работя върху AI за игра на играта Dots (връзка). Целта е да премахнете възможно най-много точки, като свържете точки с подобен цвят с линия. Прегледах дъската и групирах всеки набор от съседни точки с един и същи цвят. Всички групи в момента споделят един и същ цвят на подчертаване (черен). Така например четирите червени точки в горния ляв ъгъл образуват една група, както и трите жълти точки в горния десен ъгъл.

Трябва да изчисля всеки възможен път през една от тези групи. Може ли някой да измисли добър алгоритъм? Как мога да избегна създаването на дублиращи се пътища?

Чувал съм, че леко модифициран DFS би бил добър в тази ситуация. Въпреки това пътищата могат да се пресичат във възли, но не могат да използват повторно ръбове. Как мога да променя съответно DFS?

Екранна снимка на GUI


java artificial-intelligence path-finding depth-first-search
person Peaches491    schedule 02.01.2014    source източник
comment
Какво представлява дублиран път? Ако A, B, C, D са възли в квадратен модел 2x2, някой от тези пътища дублира ли се за вашите цели? A-B-C-D, B-C-D-A, C-D-A-B, D-C-B-A.   -  person David    schedule 03.01.2014
comment
Предполагам, че всички тези пътища биха били еквивалентни. Въпреки това, ако имаше пета червена точка в ъгъла, определени пътеки нямаше да могат да я включат. Така че изглежда не трябва да се тревожа за дубликати, докато не бъде направено изчерпателно търсене, след което помислете за подходящо подрязване.   -  person Peaches491    schedule 03.01.2014
comment
Ако отговорът ми е бил полезен, не забравяйте да го маркирате като отговор.   -  person David    schedule 05.01.2014

Отговори (1)


arrow_upward
1
arrow_downward

Ето малко псевдо код, за да започнете. Вероятно така бих го направил. Използването на ръбове вместо възли решава ситуацията с прецизното пресичане на пътища, но извличането на ръбове е по-трудно от възлите. Трябва да картографирате индексите на ръбовете към индексите на възлите.

Ще получите всяка пътека два пъти, тъй като една пътека може да бъде премината от две посоки. Ако групите точки станат големи, помислете за подрязване на най-малко интересните пътища. Изискването за памет нараства експоненциално като 4^n, където n е броят на точките в групата. Не мога да се сетя за добър начин за добавяне на непълни пътеки, без да позволявам дубликати, но може би не се интересувате от пътеки, които завършват рано?

private LinkedList<Edge> recurse(LinkedList<Edge> path) {
    Edge last = path.getLast();
    Edge right = <get Edge to the right of last>;
    Edge bottom = <get Edge below last>;
    Edge left = <get Edge to the left of last>;
    Edge top = <get Edge above last>;
    if( right && !path.contains(right) ) {
        LinkedList<Edge> ps = path.clone();  // NOTE: check if the built-in clone() function does a shallow copy
        ps.addLast( right );
        paths.add( recurse(ps) );
    }
    if( bottom && !path.contains(bottom) ) {
        ...
    }
    if( left && !path.contains(left) ) {
        ...
    }
    if( top && !path.contains(top) ) {
        ...
    }
    return path;
}
person David    schedule 02.01.2014
comment
Това е основно това, което накрая направих. Ще публикувам повече подробности, след като го завърша - person Peaches491; 07.01.2014