| dbo:abstract
|
- تعد خوارزمية الجار الأقرب إحدى أولى الخوارزميات التي تم تقديمها لحل مشكلة البائع المتجول. حيث يبدأ البائع من مدينة عشوائية ثم يزور أقرب المدن له بشكل مستمر حتى يكمل زيارة جميع المدن. تكون الجولة الناتجة عن الخوارزمية قصيرة عادة، لكنها لا تمثل الحل المثالي لهذه المشكلة. (ar)
- Die Nearest-Neighbor-Heuristik („Nächster-Nachbar-Heuristik“) ist ein heuristisches Eröffnungsverfahren aus der Graphentheorie und wird unter anderem zur Approximation einer Lösung des Problems des Handlungsreisenden verwendet. Von einem Knoten als Startpunkt ausgehend wird die minimalgewichtete benachbarte Kante zum nächsten Knoten gewählt. Dieses wird sukzessive fortgesetzt, bis alle Knoten zu einem Hamiltonschen Kreis zusammengefasst wurden. Im Allgemeinen liefert dieser Greedy-Algorithmus nicht die beste Lösung. Dies liegt hauptsächlich daran, dass der Startknoten und der Endknoten zu keinem Zeitpunkt berücksichtigt werden und anstatt dessen eine mögliche große Distanz zwischen ihnen in Kauf genommen wird. In der Tat können Beispiele mit beliebig weit vom Optimum entfernten Lösungen konstruiert werden. Indem iterativ jeder einzelne Knoten des Graphen jeweils einmal als Startknoten zur Ermittlung der Gewichtung des jeweilig entstehenden Pfades gewählt wird und diese abschließend miteinander verglichen werden, wird das Verfahren besser. Jedoch entspricht diese All Nearest-Neighbor-Heuristik bereits der Komplexitätsklasse . (de)
- El algoritmo del vecino más próximo fue, en las ciencias de la computación, uno de los primeros algoritmos utilizados para determinar una solución para el problema del viajante. Este método genera rápidamente un camino corto, pero generalmente no el ideal. Abajo está la aplicación del algoritmo del vecino más próximo al problema del viajante. Estos son los pasos del algoritmo: 1.
* elección de un vértice arbitrario respecto al vértice actual. 2.
* descubra la arista de menor peso que ya este conectada al vértice actual y a un vértice no visitado V. 3.
* convierta el vértice actual en V. 4.
* marque V como visitado. 5.
* si todos los vértices del dominio estuvieran visitados, cierre el algoritmo. 6.
* vaya al paso 2. La secuencia de los vértices visitados es la salida del algoritmo. El algoritmo del vecino más próximo es fácil de implementar y ejecutar rápidamente, pero algunas veces puede perder rutas más cortas, que son fácilmente notadas con la visión humana, debido a su naturaleza más "ávida". Como norma general, si los últimos pasos del recorrido son comparables en longitud al de los primeros pasos, el recorrido es razonable; si estos son mucho mayores, entonces es probable que existan caminos mucho mejores. (es)
- The nearest neighbour algorithm was one of the first algorithms used to solve the travelling salesman problem approximately. In that problem, the salesman starts at a random city and repeatedly visits the nearest city until all have been visited. The algorithm quickly yields a short tour, but usually not the optimal one. (en)
- 最近傍法（さいきんぼうほう、英: nearest neighbor algorithm）とは、巡回セールスマン問題を解くのに使われた最初のアルゴリズムの1つ。素早く短い経路を求められるが、最短でないことが多い。 (ja)
- Алгоритм ближайшего соседа — один из простейших эвристических алгоритмов решения задачи коммивояжёра. Относится к категории «жадных» алгоритмов. Формулируется следующим образом: Пункты обхода плана последовательно включаются в маршрут, причем каждый очередной включаемый пункт должен быть ближайшим к последнему выбранному пункту среди всех остальных, ещё не включенных в состав маршрута. Алгоритм прост в реализации, быстро выполняется, но, как и другие «жадные» алгоритмы, может выдавать неоптимальные решения. Одним из эвристических критериев оценки решения является правило: если путь, пройденный на последних шагах алгоритма, сравним с путём, пройденным на начальных шагах, то можно условно считать найденный маршрут приемлемым, иначе, вероятно, существуют более оптимальные решения. Другой вариант оценки решения заключается в использовании алгоритма (lower bound algorithm). Для любого количества городов, большего трёх, в задаче коммивояжёра можно подобрать такое расположение городов (значение расстояний между вершинами графа и указание начальной вершины), что алгоритм ближайшего соседа будет выдавать наихудшее решение. (ru)
- Algorytm najbliższego sąsiada (ang. nearest neighbour algorithm, NN) – algorytm zachłanny służący do rozwiązywania problemu komiwojażera polegający na odwiedzaniu, począwszy od wybranego wierzchołka, wierzchołka znajdującego się najbliżej wierzchołka ostatnio odwiedzonego. Dla grafu pełnego o n wierzchołkach złożoność czasowa algorytmu wynosi. (pl)
- O algoritmo do vizinho mais próximo foi, na ciência da computação, um dos primeiros algoritmos utilizados para determinar uma solução para o problema do problema do caixeiro viajante. Ele gera rapidamente um caminho curto, mas geralmente não o ideal. Abaixo está a aplicação do algoritmo do vizinho mais próximo ao problema do caixeiro viajante. Estes são os passos do algoritmo: 1.
* escolha um vértice arbitrário como vértice atual. 2.
* descubra a aresta de menor peso que seja conectada ao vértice atual e a um vértice não visitado V. 3.
* faça o vértice atual ser V. 4.
* marque V como visitado. 5.
* se todos os vértices no domínio estiverem visitados, encerre o algoritmo. 6.
* Se não vá para o passo 2. A seqüência dos vértices visitados é a saída do algoritmo. O algoritmo do vizinho mais próximo é fácil de implementar e executar rapidamente, mas às vezes pode perder rotas mais curtas, que são facilmente notadas com a visão humana, devido à sua natureza "gananciosa". Como um guia geral, se os últimos passos do percurso são comparáveis em comprimento aos dos primeiros passos, o percurso é razoável; se eles são muito maiores, então é provável que existam percursos bem melhores. (pt)
- Алгоритм найближчого сусіда — один з перших і найбільш простих евристичних методів розв'язування задачі комівояжера. Відноситься до категорії жадібних алгоритмів. За кожен крок його виконання до знайденої частини маршруту додається нове ребро. Алгоритм припиняє роботу, коли розв'язок знайдено і не намагається його покращити. (uk)
|
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 3619 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:class
| |
| dbp:data
| |
| dbp:optimal
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- تعد خوارزمية الجار الأقرب إحدى أولى الخوارزميات التي تم تقديمها لحل مشكلة البائع المتجول. حيث يبدأ البائع من مدينة عشوائية ثم يزور أقرب المدن له بشكل مستمر حتى يكمل زيارة جميع المدن. تكون الجولة الناتجة عن الخوارزمية قصيرة عادة، لكنها لا تمثل الحل المثالي لهذه المشكلة. (ar)
- The nearest neighbour algorithm was one of the first algorithms used to solve the travelling salesman problem approximately. In that problem, the salesman starts at a random city and repeatedly visits the nearest city until all have been visited. The algorithm quickly yields a short tour, but usually not the optimal one. (en)
- 最近傍法（さいきんぼうほう、英: nearest neighbor algorithm）とは、巡回セールスマン問題を解くのに使われた最初のアルゴリズムの1つ。素早く短い経路を求められるが、最短でないことが多い。 (ja)
- Algorytm najbliższego sąsiada (ang. nearest neighbour algorithm, NN) – algorytm zachłanny służący do rozwiązywania problemu komiwojażera polegający na odwiedzaniu, począwszy od wybranego wierzchołka, wierzchołka znajdującego się najbliżej wierzchołka ostatnio odwiedzonego. Dla grafu pełnego o n wierzchołkach złożoność czasowa algorytmu wynosi. (pl)
- Алгоритм найближчого сусіда — один з перших і найбільш простих евристичних методів розв'язування задачі комівояжера. Відноситься до категорії жадібних алгоритмів. За кожен крок його виконання до знайденої частини маршруту додається нове ребро. Алгоритм припиняє роботу, коли розв'язок знайдено і не намагається його покращити. (uk)
- Die Nearest-Neighbor-Heuristik („Nächster-Nachbar-Heuristik“) ist ein heuristisches Eröffnungsverfahren aus der Graphentheorie und wird unter anderem zur Approximation einer Lösung des Problems des Handlungsreisenden verwendet. Indem iterativ jeder einzelne Knoten des Graphen jeweils einmal als Startknoten zur Ermittlung der Gewichtung des jeweilig entstehenden Pfades gewählt wird und diese abschließend miteinander verglichen werden, wird das Verfahren besser. Jedoch entspricht diese All Nearest-Neighbor-Heuristik bereits der Komplexitätsklasse . (de)
- El algoritmo del vecino más próximo fue, en las ciencias de la computación, uno de los primeros algoritmos utilizados para determinar una solución para el problema del viajante. Este método genera rápidamente un camino corto, pero generalmente no el ideal. Abajo está la aplicación del algoritmo del vecino más próximo al problema del viajante. Estos son los pasos del algoritmo: La secuencia de los vértices visitados es la salida del algoritmo. (es)
- O algoritmo do vizinho mais próximo foi, na ciência da computação, um dos primeiros algoritmos utilizados para determinar uma solução para o problema do problema do caixeiro viajante. Ele gera rapidamente um caminho curto, mas geralmente não o ideal. Abaixo está a aplicação do algoritmo do vizinho mais próximo ao problema do caixeiro viajante. Estes são os passos do algoritmo: A seqüência dos vértices visitados é a saída do algoritmo. (pt)
- Алгоритм ближайшего соседа — один из простейших эвристических алгоритмов решения задачи коммивояжёра. Относится к категории «жадных» алгоритмов. Формулируется следующим образом: Пункты обхода плана последовательно включаются в маршрут, причем каждый очередной включаемый пункт должен быть ближайшим к последнему выбранному пункту среди всех остальных, ещё не включенных в состав маршрута. (ru)
|
| rdfs:label
|
- خوارزمية الجار الأقرب (ar)
- Nearest-Neighbor-Heuristik (de)
- Algoritmo del vecino más próximo (es)
- Nearest neighbour algorithm (en)
- 最近傍法 (ja)
- Algorytm najbliższego sąsiada (pl)
- Algoritmo do vizinho mais próximo (pt)
- Алгоритм ближайшего соседа в задаче коммивояжёра (ru)
- Метод найближчого сусіда (uk)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
