Nano Hash - криптовалюты, майнинг, программирование

как я могу создать граничную систему, чтобы реализовать алгоритм Дейкстры или алгоритм A*?

Я хочу применить алгоритм Дейкстры к списку функций, предоставленных файлом geoJson. У меня есть до 100 функций. Посмотрите пример. Алгоритм листовки Дейкстры что я сделал до сих пор:

  1. извлечены все точки из объектов (переменная называется points)

2. я построил список смежности, подобный этому, используя индексы из точек, поэтому 0-1-10 будет точкой индекса 0 в точках и то же самое для 1, а третья расстояние друг от друга. 3. Я построил массив смежности, но не вижу в нем никакого применения. Пример, показанный на изображении, не является полным набором функций, я ищу только начальную точку, после чего я могу работать над остальной частью карты.

  1. все черные точки - (lat, lang)

как я могу сделать краевую систему, чтобы я мог реализовать алгоритм Дейкстры или алгоритм A *

Мой вопрос: как я могу продолжить движение от А к Б? приветствуются любые предложения.

редактировать 1: добавлен код

редактировать 2: обновленный вопрос

	var start = [34.000750, 71.485753];
            var end = [34.000937, 71.485180];
           
           	var points=[];
           	var nodes=[];
           	var features=[];
           	var adjacent=[];

           	var map = L.map('map').setView(start, 17);;

	       map.attributionControl.addAttribution('<a href="https://github.com/tomchadwin/qgis2web" target="_blank">qgis2web</a>');
        var bounds_group = new L.featureGroup([]);
        var basemap0 = L.tileLayer('http://{s}.tile.openstreetmap.org/{z}/{x}/{y}.png', {
            attribution: '&copy; <a href="http://openstreetmap.org">OpenStreetMap</a> contributors,<a href="http://creativecommons.org/licenses/by-sa/2.0/">CC-BY-SA</a>',
            maxZoom: 22
        });
        basemap0.addTo(map);
        L.geoJSON(data).addTo(map);
	       //OpenStreetMap_BlackAndWhite.addTo(map)
 	        //basemap0.addTo(map);
           	function getid(){
           		var possible = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";
           		var d = possible.charAt(Math.floor(Math.random() * possible.length));
           		while(nodes.indexOf(d) >-1){
           			 d = possible.charAt(Math.floor(Math.random() * possible.length));
           		}
        		return d;
           	}
            L.geoJSON(data, {
                onEachFeature: function(feature, layer) {
                    //console.log(feature);
                    points.push.apply(points,feature.geometry.coordinates);
                    features.push(feature.geometry.coordinates);
                   // return L.Polyline(layer, geojsonMarkerOptions);
                }
            });

            function init(){
            	var marks= [];
	            for (var i = 0; i < features.length; i++) {
	                var s = features[i];

	                //var m = L.marker([s[1],s[0]]);
	                //marks.push(m);
	                for (var j = 0; j < s.length; j++) {
	                    var k = s[j];

	                    var m = L.marker([k[1],k[0]]);
	                    m.on('click',function(e){
	                        console.log(this.getLatLng());
	                    })
	                    marks.push(m);
	                }
	               
	            }
	            var heuristik
	            for (var i = 0; i < marks.length-1; i++) {
	                var lt = marks[i].getLatLng().distanceTo(marks[i+1].getLatLng());
	                var a =i;
	                var b =i+1;
	                if(lt != 0 ){
	                console.log(a,b,lt,);

	                adjacent.push([a,b,lt]);
	                }
	                //Array.prototype.push.apply(adjacent,{a,b,lt});
	     
	            }
	            //console.log(adjacent)
            }
html,body {
		width: 100%;
		height: 100%;
		overflow: hidden;
	}
	#map{
		width: 100%;
		height: 100%;
	}	
<link rel="stylesheet" href="https://unpkg.com/[email protected]/dist/leaflet.css" />
<script src="https://unpkg.com/[email protected]/dist/leaflet.js"></script>
 <script src="https://raw.githubusercontent.com/andrewhayward/dijkstra/master/graph.js"></script>
 
 		<script></script>
		<script>
    var data = {
"type": "FeatureCollection",
"crs": { "type": "name", "properties": { "name": "urn:ogc:def:crs:OGC:1.3:CRS84" } },
"features": [
{ "type": "Feature", "properties": { "Place": "Kmc Road" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.484445376090477, 34.000556224204104 ], [ 71.484619381903997, 34.00055622349123 ], [ 71.485795423886529, 34.000556218673154 ], [ 71.486389444907786, 34.000556088482497 ] ] } },
{ "type": "Feature", "properties": { "Place": "UET Main Road" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.486384748456004, 34.002041741407623 ], [ 71.485121131034504, 34.002036564553677 ], [ 71.484897906943033, 34.002035650037541 ], [ 71.484080666224514, 34.002032301923023 ] ] } },
{ "type": "Feature", "properties": { "Place": "Road 2" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.486389444907786, 34.000556088482497 ], [ 71.486384748456004, 34.002041741407623 ], [ 71.48638137935751, 34.003043552173651 ], [ 71.486380078137188, 34.003430473641167 ], [ 71.486380045906941, 34.003440057392226 ] ] } },
{ "type": "Feature", "properties": { "Place": "Hostel Road" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.486380078137188, 34.003430473641167 ], [ 71.484890807505366, 34.00343866205165 ], [ 71.483730352446614, 34.003445042545671 ] ] } },
{ "type": "Feature", "properties": { "Place": "Commerce College Road" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.483730352446614, 34.003445042545671 ], [ 71.483792886191907, 34.003192857311085 ], [ 71.484080666224514, 34.002032301923023 ], [ 71.484445376090477, 34.000556224204104 ] ] } },
{ "type": "Feature", "properties": { "Place": "Civil Engineering" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.485795429415916, 34.000635421476822 ], [ 71.485793037373725, 34.000750625722446 ], [ 71.485761836269248, 34.000750627900693 ] ] } },
{ "type": "Feature", "properties": { "Place": "Structure Labs & Library" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.485793037373725, 34.000750625722446 ], [ 71.485824238478202, 34.000750623544199 ] ] } },
{ "type": "Feature", "properties": { "Place": "Concrete Testing Lab" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.485793037373725, 34.000750625722446 ], [ 71.485797844581057, 34.000851428955635 ], [ 71.485838646025371, 34.000851426107154 ], [ 71.485841053985538, 34.000964229932706 ] ] } },
{ "type": "Feature", "properties": { "Place": "Hydraulic Lab" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.485797844581057, 34.000851428955635 ], [ 71.485800253043891, 34.000971433036057 ], [ 71.485783452449184, 34.000971434208964 ], [ 71.485785871468138, 34.001242643641845 ], [ 71.485809872317731, 34.001242641966272 ] ] } },
{ "type": "Feature", "properties": { "Place": "Civil Parking" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.485795429415916, 34.000635421476822 ], [ 71.485529019817847, 34.000633039990753 ] ] } },
{ "type": "Feature", "properties": { "Place": "CS & IT" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.485797844581057, 34.000851428955635 ], [ 71.485181022746431, 34.000851472017921 ], [ 71.485181028778499, 34.000937875076467 ] ] } },
{ "type": "Feature", "properties": { "Place": "Earthquake Center" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.485181022746431, 34.000851472017921 ], [ 71.485181021908645, 34.000839471593132 ], [ 71.485181018725044, 34.000793869978892 ], [ 71.485046613967313, 34.000793879362114 ] ] } },
{ "type": "Feature", "properties": { "Place": "New Earthquake Center" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.485181021908645, 34.000839471593132 ], [ 71.484837809926972, 34.000841895638814 ], [ 71.484837796857477, 34.000654689011959 ], [ 71.484837795852144, 34.000640288502204 ], [ 71.484621788205772, 34.000640303582379 ] ] } },
{ "type": "Feature", "properties": { "Place": "Girls Common Room" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.485181028778499, 34.000937875076467 ], [ 71.485181035313246, 34.001031478389898 ], [ 71.485181040507527, 34.001105881023648 ] ] } },
{ "type": "Feature", "properties": { "Place": "Mechanical Engineering" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.485181040507527, 34.001105881023648 ], [ 71.485181063088987, 34.001429336832032 ] ] } },
{ "type": "Feature", "properties": { "Place": "New Earthquake Gate" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.484621788205772, 34.000640303582379 ], [ 71.484619381903997, 34.00055622349123 ] ] } },
{ "type": "Feature", "properties": { "Place": "Civil Main Gate" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.485795429415916, 34.000635421476822 ], [ 71.485795423886529, 34.000556218673154 ] ] } },
{ "type": "Feature", "properties": { "Place": "New Academic Block" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.485181063088987, 34.001429336832032 ], [ 71.485125861392447, 34.001433029533452 ], [ 71.485128269185054, 34.001543433274037 ], [ 71.48599229960297, 34.001540972868369 ], [ 71.485982728920817, 34.001965788576456 ], [ 71.485677917963386, 34.001963409771299 ], [ 71.485663520302097, 34.00200421222096 ], [ 71.485557916396317, 34.002001819508536 ], [ 71.485567513887673, 34.001961017393988 ], [ 71.485118698167781, 34.001963448812212 ], [ 71.485125876678964, 34.001651992925943 ], [ 71.485128269352614, 34.001545833359003 ] ] } },
{ "type": "Feature", "properties": { "Place": "Tennis Lawn" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.485181035313246, 34.001031478389898 ], [ 71.484926626229907, 34.001030384828667 ], [ 71.484926669794874, 34.001654406918178 ], [ 71.485125876678964, 34.001651992925943 ] ] } },
{ "type": "Feature", "properties": { "Place": "Agriculture Engineering" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.484897906943033, 34.002035650037541 ], [ 71.484890084806153, 34.002365054141571 ], [ 71.484888323226841, 34.002439237380912 ] ] } },
{ "type": "Feature", "properties": { "Place": "Chemical & Industrial Egineering" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.484888323226841, 34.002439237380912 ], [ 71.484883546063472, 34.002768782456975 ] ] } },
{ "type": "Feature", "properties": { "Place": "Main Gate Entrance" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.485118698167781, 34.001963448812212 ], [ 71.485121131034504, 34.002036564553677 ] ] } },
{ "type": "Feature", "properties": { "Place": "Computer System Parking" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.484883546063472, 34.002768782456975 ], [ 71.484888363916895, 34.003022079805255 ], [ 71.484600352381278, 34.003002899232484 ] ] } },
{ "type": "Feature", "properties": { "Place": "Computer System Engineering" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.484888363916895, 34.003022079805255 ], [ 71.484888365089802, 34.003038880399977 ], [ 71.48488837681883, 34.003206886347151 ] ] } },
{ "type": "Feature", "properties": { "Place": "Hostel Road Entrance" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.48488837681883, 34.003206886347151 ], [ 71.484888930241823, 34.003259657448353 ], [ 71.484890807505366, 34.00343866205165 ] ] } },
{ "type": "Feature", "properties": { "Place": "Canteen" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.484888930241823, 34.003259657448353 ], [ 71.485097187393905, 34.003252473383881 ] ] } },
{ "type": "Feature", "properties": { "Place": "High Tension Lab" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.484888365089802, 34.003038880399977 ], [ 71.485572389638421, 34.003043632815995 ] ] } },
{ "type": "Feature", "properties": { "Place": "New Admin Block (CMS)" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.485572389638421, 34.003043632815995 ], [ 71.485975604079186, 34.00304600475129 ] ] } },
{ "type": "Feature", "properties": { "Place": "Road 2 Gate" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.485975604079186, 34.00304600475129 ], [ 71.486088447014453, 34.003045322708608 ], [ 71.48638137935751, 34.003043552173651 ] ] } },
{ "type": "Feature", "properties": { "Place": "VC Lawn" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.486088447014453, 34.003045322708608 ], [ 71.486085990058683, 34.002789187952963 ] ] } },
{ "type": "Feature", "properties": { "Place": "Electrical Engineering" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.485572389638421, 34.003043632815995 ], [ 71.485569981549489, 34.002928984566658 ] ] } },
{ "type": "Feature", "properties": { "Place": "Provost Office" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.486085990058683, 34.002789187952963 ], [ 71.486090753237178, 34.00225932450293 ], [ 71.485711539310884, 34.002252150722143 ], [ 71.485469132237981, 34.002273768410092 ], [ 71.485303533078067, 34.00236978336995 ], [ 71.485121126788684, 34.002372196189278 ] ] } },
{ "type": "Feature", "properties": { "Place": "Electrical Lawn" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.485121126788684, 34.002372196189278 ], [ 71.484890084806153, 34.002365054141571 ] ] } },
{ "type": "Feature", "properties": { "Place": "Director of Works" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.483792886191907, 34.003192857311085 ], [ 71.483894742186976, 34.003214711632012 ] ] } }
]
}

    </script>
 
 
	 
	<div id="map">
		
	</div>

leaflet algorithm dijkstra
22.05.2017

  • Так в чем проблема? Без какого-либо кода или реальной проблемы мы не можем сделать больше, чем повторить, как работает Дейкстра, которую вы наверняка уже искали, не так ли? Кроме того, поскольку у вас, кажется, есть и начало, и цель, почему бы не использовать A* вместо Дейкстры? 23.05.2017
  • @tobias_k да, я сделал, но сложная часть состоит в том, чтобы определить стоимость каждого преимущества и двигаться к цели, я попробую A * спасибо и обновлю вопрос 23.05.2017
  • Я действительно не знаю geoJson, но если это географические координаты, разве вы не можете просто использовать евклидово расстояние между двумя точками и использовать его в качестве стоимости края? (Есть и более сложные методы вычисления расстояния на сфере, но для небольших расстояний этого должно хватить.) 23.05.2017
  • См., например. здесь для расчета расстояния на сфере с широтой/долготой 23.05.2017
  • Стоимость ребра @tobias_k доступна с использованием метода DistanceTo(), доступного в Object L.LatLng(), я думаю, что система ребер, которую я сделал, неверна, так как я беру только точку за точкой и создаю ребро, что вы можете предложить? 23.05.2017
  • Боюсь, я не могу ничего подсказать, потому что я до сих пор понятия не имею, в чем ваша проблема. Дело не в алгоритмах, не в функции стоимости, ну и что еще? Возможно, вам следует показать часть вашего кода и, возможно, несколько примеров ввода и (фактического и ожидаемого) вывода. 23.05.2017
  • @tobias_k я добавил код + существующий алгоритм Дейкстры на javascript, я ищу только краевую систему, чтобы я мог ее реализовать 24.05.2017

Ответы:


1

Ваш вопрос слишком широк. Вы не указываете платформу (собираетесь ли вы вычислять кратчайший путь в веб-браузере? В бэкэнде JS? В таблице БД PostGIS со столбцами GeoJSON?), так что это заставляет нас гадать. Обратите внимание, что «функции листовки» не добавляют никакой информации, так как Leaflet также может загружать данные из разных источников данных и не гарантирует, что вы будете вычислять кратчайшие пути на стороне внешнего интерфейса.

Уже существуют сотни реализаций алгоритмов поиска пути, поэтому:

  • Для веб-браузера я бы выбрал https://github.com/perliedman/geojson-path-finder , реализующий старую добрую Дейкстру
  • Для серверной службы я бы выбрал OSRM https://github.com/Project-OSRM/osrm-backend и его замечательный алгоритм сокращения границ.
  • Для расчета маршрута на уровне хранилища данных одним из очевидных вариантов является pgRouting http://pgrouting.org/. Двенадцать разных алгоритмов? Да, пожалуйста.
23.05.2017
  • спасибо, я думаю, что поиск пути geojson от Пера Лидмана - правильный выбор для меня. 23.05.2017
  • я попробовал поиск пути geojson Пера Лидмана, он у меня не работает + отсутствие документации, мне нравится использовать граничную систему и создавать свой собственный алгоритм, как я могу это сделать, есть предложения? , моя система ребер неверна! , я не могу использовать следующий узел как ребро между двумя узлами 24.05.2017

    • 2

    после того, как решение было возможно только с использованием существующего пакета NodeJs Per Liedman https://github.com/perliedman/geojson-path-finder .

    06.06.2017
    Новые материалы
    Кластеризация: более глубокий взгляд
    Кластеризация — это метод обучения без учителя, в котором мы пытаемся найти группы в наборе данных на основе некоторых известных или неизвестных свойств, которые могут существовать. Независимо от..
    Как написать эффективное резюме
    Предложения по дизайну и макету, чтобы представить себя профессионально Вам не позвонили на собеседование после того, как вы несколько раз подали заявку на работу своей мечты? У вас может..
    Частный метод Python: улучшение инкапсуляции и безопасности
    Введение Python — универсальный и мощный язык программирования, известный своей простотой и удобством использования. Одной из ключевых особенностей, отличающих Python от других языков, является..
    Как я автоматизирую тестирование с помощью Jest
    Шутка для победы, когда дело касается автоматизации тестирования Одной очень важной частью разработки программного обеспечения является автоматизация тестирования, поскольку она создает..
    Работа с векторными символическими архитектурами, часть 4 (искусственный интеллект)
    Hyperseed: неконтролируемое обучение с векторными символическими архитектурами (arXiv) Автор: Евгений Осипов , Сачин Кахавала , Диланта Хапутантри , Тимал Кемпития , Дасвин Де Сильва ,..
    Понимание расстояния Вассерштейна: мощная метрика в машинном обучении
    В обширной области машинного обучения часто возникает необходимость сравнивать и измерять различия между распределениями вероятностей. Традиционные метрики расстояния, такие как евклидово..
    Обеспечение масштабируемости LLM: облачный анализ с помощью AWS Fargate и Copilot
    В динамичной области искусственного интеллекта все большее распространение получают модели больших языков (LLM). Они жизненно важны для различных приложений, таких как интеллектуальные..