Учитывая {пункт отправления, пункт назначения} объекты, найти все пути из одного места на другое


У меня есть объект такой:

[
   {
     origin: 'a',
     destination: 'b'
   },
   {
     origin: 'a',
     destination: 'c',
   },
   {
     origin: 'b',
     destination: 'c'
   },
   {
     origin: 'b',
     destination: 'd'
   },
   {
     origin: 'd',
     destination: 'c'
   },
   {
     origin: 'd',
     destination: 'e'
   }
];

учитывая происхождение и назначение мне нужно найти все пути, чтобы получить там.

Так что это мой код:

function getDestinations(origin, destinationEnd) {
  let destinations = payloads.filter(payload => payload.origin === origin);
  destinations = destinations.map(destination => {
    const destinationsRecursive = getDestinations(destination.destination, destinationEnd);
    if (destinationsRecursive.length) {
      return Object.assign({}, destination, {
        next: destinationsRecursive
      });
    } else if (destination.destination === destinationEnd){
      return Object.assign({}, destination, {
        end: true
      });
    }
  })
  destinations = destinations.filter(destination => destination !== undefined)
  return destinations;
}

Назвав для примера getDestinations('a', 'c'); вернется в этом:

[
  {
    "origin": "a",
    "destination": "b",
    "next": [
      {
        "origin": "b",
        "destination": "c",
        "end": true
      },
      {
        "origin": "b",
        "destination": "d",
        "next": [
          {
            "origin": "d",
            "destination": "c",
            "end": true
          }
        ]
      }
    ]
  },
  {
    "origin": "a",
    "destination": "c",
    "end": true
  }
]

Что же вам улучшить мой код, чтобы сделать то же лучше?



272
6
задан 18 февраля 2018 в 09:02 Источник Поделиться
Комментарии
2 ответа

Поэтому сначала быстрый рефакторинг объекта ввода.

const Links = links => links.split(",").map(link => ({origin: link[0], dest : link[1]}));

Так что теперь ссылки, созданные с помощью Links("ab,bc,ac"); что легче иметь дело.


Циклы никогда не закончится.

Эта проблема не так проста, как кажется на первый взгляд.

Все алгоритмы поиска пути должны быть известны пути, которые ведут по кругу.

Вашу проблему "ab,ac,bc,bd,dc,de" и решения для этого "abc", "abdc"и "ac". но если мы изменим в прошлом ссылке "da" мы создаем циклическую ссылку. Ваш код будет следовать "abdabdabdab...." и так далее до тех пор, пока переполнение стека.

В большинстве рекурсивных проблем, где вы столкнетесь с циклической ссылкой, Вы можете легко избежать бесконечной рекурсии, просто отслеживая объекты, которые вы уже ссылаются. Окончание рекурсии, когда вы обнаружите, что ссылка уже ездил.

Но ваша проблема требует от всех путей, что усложняет проблему (на самом деле невозможно, так как циклические ссылки создать бесконечное путей).

Рассмотрим ссылки "ab,ac,bc,bd,dc,da"

Он имеет следующие решения


  1. АВ, ВС

  2. АВ, БД, ДК

  3. АВ, БД, да, ас

  4. переменного тока

Если мы отметили все ездил потом 3 будет Марк ссылке ac как путешествовал и таким образом заблокировать решение 4.

Примечание: это решение включает в себя как можно больше связей, не повторяясь.

Следующие не является допустимым решением, поскольку "ad" повторяется


  1. АВ, БД, да, АВ, ВС

В настоящее время функции разбился при циклических ссылок.

Обратно в код.

Теперь давайте иили код. Код слишком сложный и очень трудно читать.


function getDestinations(origin, destinationEnd) {
let destinations = payloads.filter(payload => payload.origin === origin);
destinations = destinations.map(destination => {
const destinationsRecursive = getDestinations(destination.destination, destinationEnd);
if (destinationsRecursive.length) {
return Object.assign({}, destination, {
next: destinationsRecursive
});
} else if (destination.destination === destinationEnd){
return Object.assign({}, destination, {
end: true
});
}
})
destinations = destinations.filter(destination => destination !== undefined)
return destinations;
}

Рефакторинг.


  1. Какой-то плохой должен именования фиксации

payload становится links и вы используете назначения в виду ссылку, мы можем сократить destinationEnd как dest и getDestinations больше смысла, как getPaths С destinationsRecursive лучше назвать paths


  1. Некоторые повторы удалить

Фильтр ссылки, карта, фильтров могут быть соединены.

Также Object.assign немного шумно, вы можете использовать {...obj} сделать то же самое.

Так что теперь функция выглядит как

function getPaths(origin, dest) {
return links
.filter(link => link.origin === origin)
.map(link => {
const paths = getPaths(link.dest, dest);
if (paths.length) {
return {...link, more: paths};
} else if (link.dest === dest){
return {...link, end: true};
}
})
.filter(link => link !== undefined);
}

Который намного более читаемым.

Производительности

Сейчас проблема производительности. mapи filter оба медленно и использовать больше памяти, чем необходимо. Каждый рекурсивный вызов не освобождает память до выхода, который происходит в конце поисков. Плюс все те пути, которые не являются частью решения, которое можно отфильтровать каждой итерации

Более быстрым способом, используя простой цикл и изменение, когда вы создаете новый путь, поэтому вам не нужно содержать пути, что деваться не куда.

function solvePaths(start, end, paths = []) {
for (const link of links) {
if (link.origin === start) {
if (link.dest === end) {
paths.push({...link, end : true});
} else {
const tryPath = solvePath(link.dest, end);
if (tryPath.length) { paths.push({...link, more: tryPath}) }
}
}
}
return paths;
}

Это позволяет создавать бесконечные копии массива ссылок, через фильтр и методами карте. Это также решает проблему пути, потерпеть неудачу.

Теперь решить проблему циклической ссылки

Для этого вам нужно отслеживать пройденный путь до каждого пункта назначения.

Я создал стек, который отслеживает текущий путь ссылки "путешествовал". Когда нашли крайних точках текущие ссылки извлекаются из стека ездил, так что ссылки можно использовать для другой путь к месту назначения.

Код в примере ниже.

Ну я думаю, что он работает, он останавливает аварии, считает ли она всех решений может нужно какое-то очень глубокого исследования, которое выходит за рамки данного ответа.

Обновленный фрагмент кода

Я хотел быть уверенным, что функция работала так сделал некоторые испытания, и пока я делал это, я понял, что дальнейшее улучшение может быть сделано.

Проблема в том, что каждый шаг требует весь массив ссылок будет повторяться, проверяя, если каждое звено имеет правильное происхождение.

Что может быть переложена на создание links массив. С помощью Map индексируется origin позволяют основной цикл только петли по одной с правильным происхождением (links.origins(start) возвращает существующий массив links С происхождения start). Это значительное увеличение производительности.



function createLinks(links) {
const byOrigin = new Map();
links = links.split(",").map(link => {
const origin = link[0];
const linkObj = {dest : link[1], origin};
const origins = byOrigin.get(origin);
if (!origins) { byOrigin.set(origin, [linkObj]) }
else { origins.push(linkObj) }
return linkObj;
})
links.origins = origin => (origin = byOrigin.get(origin)) ? origin : [];
return links;
}

function solvePath(start, end, links) {
const traveled = [];
return (function solvePath(start, end, paths = []) {
for (const link of links.origins(start)) {
if (!traveled.includes(link)) {
if (link.dest === end) { paths.push({...link}) }
else {
traveled.push(link);
const more = solvePath(link.dest, end);
if (more.length) { paths.push({...link, more}) }
traveled.pop();
}
}
}
return paths;
}) (start, end);
}

function show(paths, trek, treks = []){
for (const path of paths) {
if (path.more) { show(path.more, (trek === null ? path.origin : trek) + "> "+ path.dest,treks) }
else { treks.push((trek ? trek : path.origin) + "> " + path.dest) }
}
return treks;
}

const _$ = (type,props)=>document.body.appendChild(Object.assign(document.createElement(type),props));

const theMap = "AB,AC,BC,BD,DC,DE,EC,DA,ED,EG,GD";
_$("div",{textContent : "Links : " + theMap});
show(
solvePath("A","C",createLinks(theMap))
,null
).forEach(path=>_$("div",{textContent : path}))




6
ответ дан 19 февраля 2018 в 04:02 Источник Поделиться

Вы застряли с этой структурой данных? Это приводит к большому количеству ненужных массив итерации..

В результате структура данных программно полезной? Похоже, вы все еще должны сделать некоторые преобразования по ней представить в вид каким-либо значимым образом.

1
ответ дан 19 февраля 2018 в 02:02 Источник Поделиться