![]() |
Наидлиннейший путь в графе(ну или не самый короткий)
Есть граф. Если из одной вершины можно попасть в другую,то в матрице смежности 1, если нельзя или же элемент [i][i] то 0.
Функция : Код AS3:
как переделать функцию под максимальный путь? |
Очередная жесть. Кто писал эту функцию?
Где хоть один комментарий? О каких путях идет речь? Откуда в нее передаются данные? Я сильно удивлюсь, если кто-то тут ответит на этот вопрос при таком раскладе. |
Добавил комментарии.
Функцию писал я. Цитата:
|
Какая изначально задача решается?
Кстати, не знаю, что там за граф, но в графе с циклом длина максимального пути стремится к бесконечности. |
Проблема с восприятием такого кода в том, что вы используете непонятные названия для переменных / очень неспецифические типы. Кроме того, есть вещи, которые, хоть и будут работать, их никто не делает, т.как они бессмысленны, например сравнивать булевые значения с переменными булевого типа - if (variable == true) - бессмысленное выражение, т.как достаточно было if (variable). Кроме того, существует традиция, согласно которой инфиксные опереаторы обрамляюстся пробелами с двух сторон, а префиксный или постфиксные - нет. Это значит, что -i или i++ нужно писать слитно, а i == j нужно писать раздельно. Это не ошибка, но заставляет читающего "спотыкаться".
К сожалению я недостаточно знаком с графами, чтобы что-то посоветовать по сути вопроса. |
Это NP-полная задача. Т.е. перебор (что долго), либо эвристики или что-то подобное (что не гарантирует максимальности).
|
Вобщем так: я пишу игру точки,думаю все знают,что это такое. И для обвода точек, мне и нужно находить этот наидлинейший путь/цикл.
Я пытался использовать разные методы для графов..не очень получается,по идее надо написать рекурсивную функцию.Кто-нибудь может помочь.Исходные данные для функции это матрица смежности. |
хм... можете посмотреть так называемый "жадный алгоритм" может он и сойдет.
|
берём астар и ставим отрицательные веса.
|
Если те точки, в которые я играл, то нужна наибольшая площадь, а не путь.
Я бы сделал так: охватываем прямоугольником, который затем скукоживаем, пока не получим подходящую охваченную область (когда все точки периметра - наши - это она). Довольно муторно, но вроде реализуемо. Или (по идее легче) - берём самую верхнюю точку и обходим из неё область по часовой стрелке. Если по завершению обхода отбросить висячие концы, то должно выйти типа того, что надо. Если не выходит, то выкидываем из рассмотрения пройденные точки и назначаем новую верхнюю точку. |
| Часовой пояс GMT +4, время: 03:36. |
Copyright © 1999-2008 Flasher.ru. All rights reserved.
Работает на vBulletin®. Copyright ©2000 - 2026, Jelsoft Enterprises Ltd. Перевод: zCarot
Администрация сайта не несёт ответственности за любую предоставленную посетителями информацию. Подробнее см. Правила.