Легенда:
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
странные мысли по поводу NP-полноты 13.05.03 14:08 Число просмотров: 1221
Автор: ilnar Статус: Незарегистрированный пользователь
|
> возьмем, скажем, прямоугольную сетку сосотящую из > проволочек, соединенных в узлах, создадим разнось > потенциалов между двумя краями сетки. теперь начнем > произвольно разрезать проволочки между двумя узлами. сетка > описывает граф и задача нахождения , кратчайшего расстояния > между двумя сторонами является NP-сложной, однако до тех > пор, пока существует такой путь ток будет течь по сетке, > при этом как бы сама “природа” решает эту задачу, при этом > такое чувство, что полиномиально. > интересно что вы думаете по этому поводу :)))
подождите, если вы о задаче нахождения кратчайшего пути между двумя пунктами в графе - так эта задача полиномиальная!! Алгоритмы дейкстры, Флойда-Уоршелла на то пример
|
|
|