Форум Flasher.ru

Форум Flasher.ru (http://www.flasher.ru/forum/index.php)
-   ActionScript 3.0 (http://www.flasher.ru/forum/forumdisplay.php?f=83)
-   -   Наидлиннейший путь в графе(ну или не самый короткий) (http://www.flasher.ru/forum/showthread.php?t=160676)

Kaner 15.07.2011 22:13

Наидлиннейший путь в графе(ну или не самый короткий)
 
Есть граф. Если из одной вершины можно попасть в другую,то в матрице смежности 1, если нельзя или же элемент [i][i] то 0.


Функция :
Код AS3:

         public function maxWay2(d:Array,x:Number):Array{
 
                      //d-матрица смежности
                      //x-элемент который есть начало поиска замкнутого пути
 
                        var i:int; //счетчик
                        var j:int; //счетчик
                        var l:int=-1; //счетчик
                        var put:Array=new Array(); //туда будем добавлять номера элементов пути
                        var end:Boolean=false; //переменная для проверки окончания поиска
 
 
                        for(i=0;i<d.length;i++) //цикл по размерности матрицы смежности,т.е по кол-ву элементов в графе
                        {
                                if(d[x][i]==1) //если нашли связь с каким-то элементом то...
                                {
                                        l++; //делаем l=0
                                        put[l]=i; //записываем этот элемент в путь
                                        i=d.length; //завершаем цикл по i
                                        j=-1; // делаем -1 чтобы инкриминировать в начале следующего цикла
                                        while(end==false)
                                        {
                                                j++;
 
                                                if(d[put[l]][j]==1 && provMas(put,j)==-1) //если находим элемент, с которым есть связь у предыдущего элемента добавленного в наш путь и он
                                                  // не содержится в пути то...
                                                        {
                                                                l++;                                                       
                                                                put[l]=j; //добавляем этот элемент в путь
                                                                j=-1; //присваиваем -1 чтобы начать поиск уже для нового элемента
 
                                                        }
                                                        if(put[l]==x || j>=d.length) //критерии окончания поиска:если нашли замкнутый путь или если не нашли связь
                                                        {
                                                                end=true;
                                                        }
 
                                        }
                                }
                        }
 
                        if(put[l]==x && l!=-1) //если получили замкнутый путь и вошли  в самый первый if то возвращаем путь
                        {
                                return put;
                        }
                        return[-1,-1];
 
                }
 
                public function provMas(a:Array,sE:Object):int {
                        for(var i:int=0;i < a.length;i++)
                        {
                                if (a[i].toString()==sE.toString()) {
                                        return i;
                                }                       
                        }
                        return -1;
                }

Она ищет неминимальный путь но не всегда максимальный.
как переделать функцию под максимальный путь?

goodguy 15.07.2011 23:08

Очередная жесть. Кто писал эту функцию?
Где хоть один комментарий?
О каких путях идет речь?
Откуда в нее передаются данные?
Я сильно удивлюсь, если кто-то тут ответит на этот вопрос при таком раскладе.

Kaner 15.07.2011 23:19

Добавил комментарии.
Функцию писал я.

Цитата:

О каких путях идет речь?
о замкнутых путях. В функцию я передаю х-это должно стать началом и концом замкнутого пути если он есть

mikhailk 16.07.2011 10:51

Какая изначально задача решается?
Кстати, не знаю, что там за граф, но в графе с циклом длина максимального пути стремится к бесконечности.

wvxvw 16.07.2011 13:22

Проблема с восприятием такого кода в том, что вы используете непонятные названия для переменных / очень неспецифические типы. Кроме того, есть вещи, которые, хоть и будут работать, их никто не делает, т.как они бессмысленны, например сравнивать булевые значения с переменными булевого типа - if (variable == true) - бессмысленное выражение, т.как достаточно было if (variable). Кроме того, существует традиция, согласно которой инфиксные опереаторы обрамляюстся пробелами с двух сторон, а префиксный или постфиксные - нет. Это значит, что -i или i++ нужно писать слитно, а i == j нужно писать раздельно. Это не ошибка, но заставляет читающего "спотыкаться".
К сожалению я недостаточно знаком с графами, чтобы что-то посоветовать по сути вопроса.

-De- 16.07.2011 18:07

Это NP-полная задача. Т.е. перебор (что долго), либо эвристики или что-то подобное (что не гарантирует максимальности).

Kaner 10.08.2011 17:27

Вобщем так: я пишу игру точки,думаю все знают,что это такое. И для обвода точек, мне и нужно находить этот наидлинейший путь/цикл.
Я пытался использовать разные методы для графов..не очень получается,по идее надо написать рекурсивную функцию.Кто-нибудь может помочь.Исходные данные для функции это матрица смежности.

t4arty 10.08.2011 17:57

хм... можете посмотреть так называемый "жадный алгоритм" может он и сойдет.

Котяра 10.08.2011 18:11

берём астар и ставим отрицательные веса.

-De- 10.08.2011 18:20

Если те точки, в которые я играл, то нужна наибольшая площадь, а не путь.
Я бы сделал так: охватываем прямоугольником, который затем скукоживаем, пока не получим подходящую охваченную область (когда все точки периметра - наши - это она). Довольно муторно, но вроде реализуемо.
Или (по идее легче) - берём самую верхнюю точку и обходим из неё область по часовой стрелке. Если по завершению обхода отбросить висячие концы, то должно выйти типа того, что надо. Если не выходит, то выкидываем из рассмотрения пройденные точки и назначаем новую верхнюю точку.


Часовой пояс GMT +4, время: 03:36.

Copyright © 1999-2008 Flasher.ru. All rights reserved.
Работает на vBulletin®. Copyright ©2000 - 2026, Jelsoft Enterprises Ltd. Перевод: zCarot
Администрация сайта не несёт ответственности за любую предоставленную посетителями информацию. Подробнее см. Правила.