Общее·количество·просмотров·страницы

Java Dev Notes - разработка на Java (а также на JavaScript/Python/Flex и др), факты, события из АйТи

среда, 19 января 2011 г.

Графы. Класс ориентированного графа.

Рассмотрим Java-класс, который представляет ориентированный граф. Также как и посте Графы. Простой класс графа (неориентированного), класс имеет такие же особенности:

  • Внутреннее представление графа - список смежности

  • Вершины однозначно идентифицируются строковыми идентификаторами (именами). Не допускается двух вершин с одинаковым именем

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

  • Для того, чтобы добавить ребро между двумя вершинами, необязательно предварительно добавлять вершины в граф. Несуществующие вершины будут созданы автоматически



Да и вообще, данный класс получается путем небольшой модификации класса UndirectedGraph, а именно - немножко изменяется метод addEdge, который добавляет ребро в список смежности лишь одной вершины, а не двух. Итак, код следующий:

import java.util.Map;
import java.util.List;
import java.util.HashMap;
import java.util.ArrayList;
import java.util.Collections;
 
public class DirectedGraph {
 
private HashMap<String, List<String>> vertexMap = new HashMap<String, List<String>>();
 
public void addVertex(String vertexName) {
if (!hasVertex(vertexName)) {
vertexMap.put(vertexName, new ArrayList<String>());
}
}
 
public boolean hasVertex(String vertexName) {
return vertexMap.containsKey(vertexName);
}
 
public boolean hasEdge(String vertexName1, String vertexName2) {
if (!hasVertex(vertexName1)) return false;
List<String> edges = vertexMap.get(vertexName1);
return Collections.binarySearch(edges, vertexName2) != -1;
}
 
public void addEdge(String vertexName1, String vertexName2) {
if (!hasVertex(vertexName1)) addVertex(vertexName1);
if (!hasVertex(vertexName2)) addVertex(vertexName2);
List<String> edges1 = vertexMap.get(vertexName1);
edges1.add(vertexName2);
Collections.sort(edges1);
}
 
public Map<String, List<String>> getVertexMap() {
return vertexMap;
}
}

вторник, 18 января 2011 г.

Графы. Поиск в глубину (depth-first search, DFS)

Рассмотрим алгоритм поиска в глубину в графе (depth-first search). Поиск в глубину - один из методов обхода графа. Алгоритм поиска описывается следующим образом: для каждой не пройденной вершины необходимо найти все не пройденные смежные вершины и повторить поиск для них. Используется в следующих задачах:

  • алгоритмы поиска одно- и двусвязных компонент

  • топологическая сортировка

  • поиск путей в графе

  • поиск лексикографически первого пути в графе

  • проверка графа на ацикличность и нахождение цикла

  • поиск мостов (мостом называется такое ребро, удаление которого делает граф несвязным)


Рассмотрим следующий граф:


Для него нужно выполнить следующее:
1) сделать поиск в глубину. На каждом шаге из нескольких доступных вершин выбирать лексикографически первую вершину.
2) проставить для каждой вершины время входа и время выхода из нее
3) распечатать вершины в порядке входа (т.е. отсортировать по возрастанию времени входа), указав для каждой вершины время входа и выхода

Сначал создадим этот граф:
graph = new UndirectedGraph();
graph.addEdge("A", "B");
graph.addEdge("A", "E");
graph.addEdge("B", "C");
graph.addEdge("B", "E");
graph.addEdge("C", "F");
graph.addEdge("E", "F");
graph.addEdge("F", "I");
 
graph.addEdge("D", "G");
graph.addEdge("D", "H");
graph.addEdge("G", "H");

Затем, поскольку нужно выбирать лексикографически первую вершину, возьмем список вершин и отсортируем их по имени по возрастанию. В результате, список vertexList будет содержать имена всех вершин графа, отсортированные лексикографически:

Map<String, List<String>> vm = graph.getVertexMap();
List<String> vertexList = new ArrayList<String>(vm.size());
vertexList.addAll(vm.keySet());
Collections.sort(vertexList);
 

Теперь пришло время выполнить поиск в глубину:

for (String v : vertexList) {
dfs(v);
}

Наконец, выполняем последний пункт задания - распечатываем вершины в порядке входа:

for (Map.Entry<String, Mark> entry : visitedMap.entrySet()) {
Mark m = entry.getValue();
System.out.format("%1$s : (%2$d, %3$d)\n", entry.getKey(), m.pre, m.post);
}

Здесь мы используем вспомогательный класс Mark, который содержит время входа и выхода:

static class Mark {
public Mark(int pre, int post) {
this.pre = pre;
this.post = post;
}
public int pre;
public int post;
};

Хеш-таблица visitedMap содержит посещенные вершины графа и соотвествующее время входа/выхода. В качестве реализации visitedMap мы выбрали java.util.LinkedHashMap. Эта реализация позволяет перебрать все добавленные в хеш-таблицу элементы в том порядке, в котором они были добавлены (а не в произвольном порядке, как обычная java.util.HashMap). Это как раз и дает нам возможность распечатать вершины графа в порядке входа.

Теперь рассмотрим сам алгоритм поиска в глубину:

static void dfs(String vertexName) {
if (visitedMap.containsKey(vertexName)) return;
 
// set pre (time of enter)
visitedMap.put(vertexName, new Mark(counter,-1));
counter++;
 
// retrieve adjacent vertices
Map<String, List<String>> vm = graph.getVertexMap();
List<String> adjacentVertices = vm.get(vertexName);
 
for (String v : adjacentVertices) {
if (visitedMap.containsKey(v)) continue;
dfs(v);
}
 
// set post (time of exit)
Mark m = visitedMap.get(vertexName);
m.post = counter++;
}

Мне кажется, что код и комментарии в нем говорят сами за себя :-)

Наконец, приведем полный исходный код решения задачи (Problem1.java):

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedHashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
import java.util.List;
import java.util.Map;
 
public class Problem1 {
 
static class Mark {
public Mark(int pre, int post) {
this.pre = pre;
this.post = post;
}
public int pre;
public int post;
};
 
// our graph
static UndirectedGraph graph;
// map of visited vertices
static Map<String, Mark> visitedMap = new LinkedHashMap<String, Mark>();
// time counter
static int counter = 1;
 
public static void main(String[] args) {
 
graph = new UndirectedGraph();
graph.addEdge("A", "B");
graph.addEdge("A", "E");
graph.addEdge("B", "C");
graph.addEdge("B", "E");
graph.addEdge("C", "F");
graph.addEdge("E", "F");
graph.addEdge("F", "I");
 
graph.addEdge("D", "G");
graph.addEdge("D", "H");
graph.addEdge("G", "H");
 
Map<String, List<String>> vm = graph.getVertexMap();
 
List<String> vertexList = new ArrayList<String>(vm.size());
vertexList.addAll(vm.keySet());
Collections.sort(vertexList);
 
for (String v : vertexList) {
dfs(v);
}
 
for (Map.Entry<String, Mark> entry : visitedMap.entrySet()) {
Mark m = entry.getValue();
System.out.format("%1$s : (%2$d, %3$d)\n", entry.getKey(), m.pre, m.post);
}
}
 
static void dfs(String vertexName) {
if (visitedMap.containsKey(vertexName)) return;
 
// set pre (time of enter)
visitedMap.put(vertexName, new Mark(counter,-1));
counter++;
 
// retrieve adjacent vertices
Map<String, List<String>> vm = graph.getVertexMap();
List<String> adjacentVertices = vm.get(vertexName);
 
for (String v : adjacentVertices) {
if (visitedMap.containsKey(v)) continue;
dfs(v);
}
 
// set post (time of exit)
Mark m = visitedMap.get(vertexName);
m.post = counter++;
}
}


При запуске получаем следующий вывод:

$>java Problem1
A : (1, 12)
B : (2, 11)
C : (3, 10)
F : (4, 9)
E : (5, 6)
I : (7, 8)
D : (13, 18)
G : (14, 17)
H : (15, 16)


Или, в графическом виде:


Дополнительные ссылки:
Поиск в глубину - Википедия
Поиск в глубину в графе - MAXimal

вторник, 11 января 2011 г.

Графы. Простой класс графа (неориентированного)

В ближайших постах я собираюсь рассмотреть некоторые алгоритмы и задачи на графах. В основном, будет использоваться Java. Поэтому полезно будет иметь класс, который бы предоставлял бы граф в коде и обеспечивал бы простейшие операции над ним. Рассмотрим класс UndirectedGraph, который содержит представление неориентированного графа:

import java.util.Map;
import java.util.List;
import java.util.HashMap;
import java.util.ArrayList;
import java.util.Collections;
 
public class UndirectedGraph {
 
private HashMap<String, List<String>> vertexMap = new HashMap<String, List<String>>();
 
public void addVertex(String vertexName) {
if (!hasVertex(vertexName)) {
vertexMap.put(vertexName, new ArrayList<String>());
}
}
 
public boolean hasVertex(String vertexName) {
return vertexMap.containsKey(vertexName);
}
 
public boolean hasEdge(String vertexName1, String vertexName2) {
if (!hasVertex(vertexName1)) return false;
List<String> edges = vertexMap.get(vertexName1);
return Collections.binarySearch(edges, vertexName2) != -1;
}
 
public void addEdge(String vertexName1, String vertexName2) {
if (!hasVertex(vertexName1)) addVertex(vertexName1);
if (!hasVertex(vertexName2)) addVertex(vertexName2);
List<String> edges1 = vertexMap.get(vertexName1);
List<String> edges2 = vertexMap.get(vertexName2);
edges1.add(vertexName2);
edges2.add(vertexName1);
Collections.sort(edges1);
Collections.sort(edges2);
}
 
public Map<String, List<String>> getVertexMap() {
return vertexMap;
}
}


Отметим некоторые особенности:

  • Внутреннее представление графа - список смежности

  • Вершины однозначно идентифицируются строковыми идентификаторами (именами). Не допускается двух вершин с одинаковым именем

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

  • Для того, чтобы добавить ребро между двумя вершинами, необязательно предварительно добавлять вершины в граф. Несуществующие вершины будут созданы автоматически

понедельник, 3 января 2011 г.

Искусственный интеллект. Алгоритм имитации отжига

Алгоритм имитации отжига (Simulated annealing) — это общий алгоритмический метод решения задачи глобальной оптимизации, особенно дискретной и комбинаторной оптимизации. Один из примеров методов Монте-Карло.

Алгоритм метода показан на следующем рисунке:


График этой функции показан на следующем рисунке:


Сначала создается начальное решение. Для большинства задач, это может быть случайным образом выбранное решение. Затем созданное решение оценивается - в результате, получаем число, выражающее оценку данного решения. Также проставляем температуру в начальное значение. В ходе поиска оптимального решения мы будем все время уменьшать температуру. Есть разные способы уменьшения температуры: экспоненциальный (T[i+1] = k*T[i], k<1), линейный (T[i+1] = T[i] - dT) и др. Эти способы называются расписаниями охлаждения (cooling schedules).

Затем решение случайным образом модифицируется. Для этого создается еще одна копия текущего решения (current solution), которое называется рабочим решением (working solution). Эта копия и модифицируется случайным образом.

Теперь мы имеем два экземпляра решения - текущее и рабочее. Производится оценка рабочего решения. В результате, получаем еще одно число. Оценка рабочего решения сравнивается с оценкой текущего решения. Если оценка рабочего решения лучше, то мы копируем рабочее решение в текущее решения, затем уменьшаем температуру и переходит к следующей итерации цикла.

Если же оценка рабочего решения хуже, то мы обращаемся к критерию приемки данного решения (acceptance criteria). Вероятность того, что мы примем данное (рабочее) решение зависит от разницы в оценках между рабочим и текущим решениями, а также от текущей температуры. Данная вероятность выражается следующей формулой:


График этой функции показан на следующем рисунке:


Чем выше температура, тем больше вероятность принятия рабочего решения. И наоборот - чем меньше температура, тем меньше вероятность принятия текущего рабочего решения. Это связано с попыткой "скопировать" процессы, происходящие в металле при отжиге: при высоких температурах кристаллическая решетка металла меняется легче, чем при низких. Так и здесь: при высоких температурах текущее решение легче меняется на рабочее.

Приведем псевдокод алгоритма:

s ← s0; e ← E(s) // Initial state, energy.
sbest ← s; ebest ← e // Initial "best" solution
k ← 0 // Energy evaluation count.
while k < kmax and e < emax // While time left & not good enough:
snew ← neighbour(s) // Pick some neighbour.
enew ← E(snew) // Compute its energy.
if P(e, enew, temp(k/kmax)) > random() then // Should we move to it?
s ← snew; e ← enew // Yes, change state.
if enew < ebest then // Is this a new best?
sbest ← snew; ebest ← enew // Save 'new neighbour' to 'best found'.
k ← k + 1 // One more evaluation done
return sbest // Return the best solution found.

суббота, 1 января 2011 г.

Уголок Linux. Базовые команды. Passwd.

В настоящее время я читаю хорошую книжку от Apress: Beginning the Linux Command Line, автор Sander van Vugt. В книге очень хорошо описана работа с командной строкой Linux, описано выполнение различных действий, которой сгруппировано по темам: работа с файловой системой, работа с текстовыми редакторами, управление пользователями, менеджмент процессов, работа с сетью и т. п. Этим постом я начинаю серию "Уголок Linux", в которой будет описываться работа в среде Linux - выполнение повседневных действий, администрирование системы и т.п.

Смена пароля пользователя производится командой passwd. Если не передается имя пользователя, то команда меняет пароль текущего пользователя. Пример:

vasya@machine:~>passwd
Changing password for vasya.
Old password:
New password:
Reenter new password:
Password changed.


Из-под рута можно менять пароли других пользователей следующим образом: passwd username, т.е. передавая команде имя пользователя. Следующие опции полезны:

  • -d удаляет пароль для аккаунта

  • -l блокирует аккаунт

  • -u разблокирует аккаунт

  • -e пароль аккаунта помечается как "истекший". Юзер при следующем логине должен будет ввести новый пароль

Постоянные читатели