#java #algorithm #graph-algorithm
#java #алгоритм #граф-алгоритм
Вопрос:
Мне нужна помощь с заданием, касающимся цепочки слов BFS. Цепочка слов основана на словах из пяти букв, два слова соединяются, когда последние четыре буквы в слове x находятся в слове y. Например, climb и blimp связаны, потому что l, i, m и b в climb находятся в слове blimp.
Рекомендуется использовать directed BFS из 4-го издания алгоритмов Седжвика или модифицировать его. Код можно найти здесь: https://algs4.cs.princeton.edu/40graphs / и использовать следующий код для чтения файла данных в список слов:
BufferedReader r =
new BufferedReader(new InputStreamReader(new FileInputStream(fnam)));
ArrayList<String> words = new ArrayList<String>();
while (true) {
String word = r.readLine();
if (word == null) { break; }
assert word.length() == 5; // inputcheck, if you run with assertions
words.add(word);
}
и следующий код для чтения тестовых примеров из файла:
BufferedReader r =
new BufferedReader(new InputStreamReader(new FileInputStream(fnam)));
while (true) {
String line = r.readLine();
if (line == null) { break; }
assert line.length() == 11; // inputcheck, if you run with assertions
String start = line.substring(0, 5);
String goal = line.substring(6, 11);
// ... search path from start to goal here
}
Слова в файле данных:
their
moist
other
blimp
limps
about
there
pismo
abcde
bcdez
zcdea
bcdef
fzcde
Когда используется файл тестового примера…
other there
other their
their other
blimp moist
limps limps
moist limps
abcde zcdea
… результатом должно быть количество ребер между каждой парой слов и -1, если между словами нет пути.
1
1
-1
3
0
-1
2
Я новичок в работе с графиками, и я не уверен, как использовать BFS от Sedgewick и модифицировать его для чтения файла тестовых примеров. Любая помощь приветствуется.
Комментарии:
1. Является ли Java предпочтительным языком? Или это не имеет значения только чистый алгоритм?
2. @DanielHao Я не очень хорошо знаком с другими языками, поэтому предпочитаю Java, но это может помочь, даже если оно на другом языке.
3. можете ли вы опубликовать код, который у вас уже есть?
4. просто чтобы понять, так что алгоритм bfs обслуживается, чего вы не знаете, так это как передать файл алгоритму? это правильно?
Ответ №1:
Давайте предположим n , что это количество слов в наборе данных.
Во-первых, нам нужно построить список смежности для всех вышеперечисленных слов в соответствии с заданным условием, т. Е. Между x и есть граница y тогда и только тогда, когда последние четыре буквы x присутствуют в y . Построение этого списка смежности представляет собой операцию O (n ^ 2 * w), где w — средний размер каждого слова в наборе данных.
Во-вторых, все, что нам нужно сделать, это традиционный BFS поверх тестовых данных.
Вот main функция:
public static void main(String[] args) throws IOException {
// get words from dataset
List<String> words = readData();
// get the word pairs to test
List<List<String>> testData = getTestData();
// form an adjacency list
Map<String, List<String>> adj = getAdjacencyList(words);
// for each test, do a traditional BFS
for (List<String> test : testData) {
System.out.println(bfs(adj, test));
}
}
Вот функция для построения списка смежности в соответствии с заданным условием:
public static Map<String, List<String>> getAdjacencyList(List<String> words) {
Map<String, List<String>> adj = new HashMap<>();
for (int i = 0; i < words.size(); i) {
String word = words.get(i);
adj.put(word, adj.getOrDefault(word, new ArrayList<>()));
for (int j = 0; j < words.size(); j) {
if (i == j) continue;
int count = 0;
String other = words.get(j);
for (int k = 1; k < 5; k) {
count = other.indexOf(word.charAt(k)) != -1 ? 1 : 0;
}
// if the condition is satisfied, there exists an edge from `word` to `other`
if (count >= 4)
adj.get(word).add(other);
}
}
return adj;
}
И вот BFS:
public static int bfs(Map<String, List<String>> adj, List<String> test) {
Queue<String> q = new LinkedList<>();
Set<String> visited = new HashSet<>(); // to keep track of the visited words, since the graph is not necessarily a DAG
String start = test.get(0);
String end = test.get(1);
// if `start` and `end` words are equal
if (start.equals(end))
return 0;
q.add(start);
visited.add(start);
int count = 0;
while (!q.isEmpty()) {
count ;
int size = q.size();
for (int i = 0; i < size; i) {
String word = q.poll();
for (String val : adj.get(word)) {
if (val.equals(end))
return count; // return the number of edges
if (!visited.contains(val)) // only add the words which aren't visited yet.
q.add(val);
}
}
}
return -1; // if there isn't any edge
}
Комментарии:
1. Спасибо за ваше предложение, хотя я не уверен, как прочитать тестовые данные, чтобы добавить их в список <Список<Строка>> Тестовые данные.
2. Это не дает кратчайшего пути для abcde zcdea взгляните на мой ответ ниже, чтобы узнать, как это сделать
Ответ №2:
@The Room предоставили довольно хороший ответ, но я хочу предложить простую модификацию для части построения списка смежности, поскольку предлагаемый подход к построению списка имеет сложность O (n ^ 2), что приведет к снижению производительности для больших входных файлов.
Просто вы можете взять все возможные отсортированные шаблоны из 4 символов каждого слова и вставить их в хэш-карту с идентификатором слова (например, индекс).
Пример кода на C :
map<string , vector<int> >mappings ;
for(int i = 0 ; i < words.size(); i ){
string word = words[i].substr(0 , 4) ;
sort(word.begin() , word.end());
mappings[word].push_back(i);
for(int j = 0 ; j < 4 ; j ){
word = words[i].substr(0 , 4) ;
word[j] = words[i][4];
sort(word.begin() , word.end());
mappings[word].push_back(i);
}
}
Теперь у вас есть вектор индексов слов, которые, как вы знаете, должны иметь границу между ними и любым словом, заканчивающимся теми же 4 символами ключа вектора.
И тогда вы можете просто построить график, просто позаботившись о том, чтобы не создавать собственные циклы (избегайте создания ребра с узлом и самим собой).
Пример кода:
// Building the graph with complexity of O(n * log(no. of edges))
const int N = 100000; // Just and example
vector<int>graph[N];
for(int i = 0 ; i < words.size(); i ){
string tmp = words[i].substr(1 , 4);
sort(tmp.begin() , tmp.end());
for(int j = 0 ; j < mappings[tmp].size(); j ){
if (j == mappings[tmp][j])
continue;
graph[i].push_back(mappings[tmp][j]);
}
}
Наконец, вы можете перебрать свой тестовый файл, получить начальный и конечный индексы (при чтении файла сохраняйте каждое слово как ключ со значением его индекса), а затем применяете функцию bfs для вычисления количества ребер, как описано в ответе @The Room
Я просто хотел предложить этот ответ для людей, которым может понадобиться решение аналогичной проблемы с большими входными данными, что уменьшит сложность построения графика от O (N ^ 2) до O (N * log (количество ребер)), где N — количество слов.
Ответ №3:
Мой подход был немного другим, и в вопросе есть также тонкий нюанс, о котором я расскажу ниже:
Сначала мы создаем список смежности: (у @Volpe95 есть хорошая оптимизация для этого). Используется карта узлов, где слово является ключевым.
Map<String, Node> nodes = new HashMap<>();
List<String> words = new DataHelper().loadWords("src/main/wordsInput.dat");
System.out.println(words);
for (int i = 0; i < words.size(); i ) {
String l = words.get(i);
nodes.put(l, new Node(l));
}
for(Map.Entry<String,Node> l: nodes.entrySet()) {
for(Map.Entry<String, Node> r:nodes.entrySet()) {
if (l.equals(r)) continue;
if (isLinkPair(l.getKey(), r.getKey())) {
Node t = nodes.get(l.getKey());
System.out.println(t);
t.addChild(nodes.get(r.getKey()));
}
}
}
Islink Pair проверяет, можно ли найти последние четыре буквы слова в возможном дочернем слове.
private static boolean isLinkPair(String l, String r) {
// last 4 chars only
for (int i = 1; i < l.length(); i ) {
if(r.indexOf(l.charAt(i)) == -1){
return false;
}
}
return true;
}
Узел хранит каждое слово и дочерние элементы, а также edgeTo, это используется для вычисления кратчайшего пути, по которому каждый узел хранит своего родителя. Этот дочерний элемент всегда будет находиться на кратчайшем пути. (Sedgewick хранит эти данные в отдельных массивах, но часто их проще группировать в классе, поскольку это облегчает понимание кода)
(Геттеры, сеттеры и т. Д. Опущены для ясности и равенства)
public class Node {
private Set<Node> children;
private String word;
private Node edgeTo;
private int visited;
public Node(String word) {
children = new HashSet<>();
this.word = word;
edgeTo = null;
}
}
Алгоритм BFS, основанный на алгоритме Седжвика, выполняет поиск по каждому узлу, его непосредственным дочерним элементам и их дочерним элементам по очереди и так далее. Каждый раз он ищет очень далеко от источника. Обратите внимание, что используется очередь, и это реализовано LinkedList в Java.
private boolean bfs(Map<String,Node> map, Node source, Node target) {
if(source == null || target == null) return false;
if(source.equals(target))return true;
Queue<Node> queue = new LinkedList<>();
source.setVisited();
queue.add(source);
while(!queue.isEmpty()) {
Node v = queue.poll();
for (Node c : v.getChildren()) {
if(c.getVisited()==0){
System.out.println("visiting " c);
c.setVisited();
c.setEdgeTo(v);
if(c.equals(target)) {
return true;
}
queue.add(c);
}
}
}
return false;
}
Обратите внимание, что v является родительским, а c — его дочерними элементами. setEdgeTo используется для установки родительского дочернего элемента.
Наконец, мы проверяем результаты, где source и target являются исходными и целевыми словами соответственно:
BreadthFirstPaths bfs = new BreadthFirstPaths(nodes,source,target);
int shortestPath = bfs.getShortestPath(nodes,source,target);
Итак, что из нюанса, о котором я упоминал выше? Вычисление кратчайшего пути необходимо, поскольку
zcdea имеет двух родителей fzcde и bcdez, и вам нужен тот, который находится на кратчайшем пути. Для этого используйте edgeTo дочернего элемента, найдите его родительский элемент и повторяйте, пока не пройдете путь, как показано ниже. Это дочернее родительское отношение всегда будет находиться на кратчайшем пути из-за способа, которым bfs выполняет поиск от источника наружу.
// get edgeTo on target (the parent) , find this node and get its parent
// continue until the shortest path is walked or no path is found
public int getShortestPath(Map<String,Node> map, String source, String target) {
Node node = map.get(target);
int pathLength = 0;
do {
if(node == null || pathLength > map.size()) return NOPATH;
if(node.equals(map.get(source))) return pathLength;
node = map.get(node.getWord()).getEdgeTo();
pathLength ;
} while (true);
}
Всегда есть компромиссы между сложностью пространства и времени, которые необходимо учитывать и оптимизировать.