当前位置：文档之家 › Optimal Solution Tarjan’s Algorithm

Optimal Solution Tarjan’s Algorithm

  • 格式：pdf
  • 大小：449.54 KB
  • 文档页数：36

ML Workshop 2007
The Disjoint Sets Problem
goal: a data structure to maintain a partition of {0, 1, . . . , n − 1} imperative data structure: module type ImperativeUnionFind = sig type t val create : int → t val find : t → int → int val union : t → int → int → unit end
A Persistent Union-Find Data Structure
Sylvain Conchon and Jean-Christophe Filliˆtre a
Universit´ Paris Sud – CNRS e
S. Conchon & J.-C. Filliˆtre a
A Persistent Union-Find Data Structure
Persistent Union-Find
the previous solution is not adapted to backtracking no immediate undo operation copying the structure would be disastrous a solution would be a persistent data structure: module type PersistentUnionFind = sig type t val create : int → t val find : t → int → int val union : t → int → int → t end
S. Conchon & J.-C. Filliˆtre a
A Persistent Union-Find Data Structure
ML Workshop 2007
Persistent Union-Find
the previous solution is not adapted to backtracking no immediate undo operation copying the structure would be disastrous a solution would be a persistent data structure: module type PersistentUnionFind = sig type t val create : int → t val find : t → int → int val union : t → int → int → t end
S. Conchon & J.-C. Filliˆtre a
A Persistent Union-Find Data Structure
ML Workshop 2007
Persistent Arrays
to keep Tarjan’s efficiency, we need efficient persistent arrays solution known since 1978 and due to Henry Baker idea: a persistent array is either a usual array or a modification of another persistent array type α t = α data ref and α data = | Arr of α array | Diff of int × α × α t
S. Conchon & J.-C. Filliˆtre a
A Persistent Union-Find Data Structure
ML Workshop 2007
Optimal Solution: Tarjan’s Algorithm
(solution actually due to M. D. McIllroy and R. Morris, and “only” analyzed by Tarjan) within each class, elements are chained up to the representative
S. Conchon & J.-C. Filliˆtre a
A Persistent Union-Find Data Structure
ML Workshop 2007
A Persistent Version of Tarjan’s Algorithm
the same arrays as in the original solution: type t = { rank: int A.t; mutable link: int A.t } the mutable field allows path compression
S. Conchon & J.-C. Filliˆtre a
A Persistent Union-Find Data Structure
ML Workshop 2007
A Na¨ Solution ıve
module M = Map.Make(struct type t = int let compare = compare end) type t = int M.t let create n = M.empty let find m i = let rec lookup i = try lookup (M.find i m) with Not found → i in lookup i let union m i j = let ri = find m i in let rj = find m j in if ri <> rj then M.add ri rj m else m
S. Conchon & J.-C. Filliˆtre a
A Persistent Union-Find Data Structure
ML Workshop 2007
Our Solution
we propose a solution as efficient as Tarjan’s algorithm which is persistent (but uses side-effects) formally proved correct obtained by combining a data structure of persistent arrays a persistent version of Tarjan’s algorithm
ML Workshop 2007
A Persistent Version of Tarjan’s Algorithm
written independently of the structure for persistent arrays: module Make(A : PersistentArray) : PersistentUnionFind assuming module type PersistentArray = sig type α t val init : int → (int → α) → α t val get : α t → int → α val set : α t → int → α → α t end
S. Conchon & J.-C. Filliˆtre a
A Persistent Union-Find Data Structure
ML Workshop 2007
The Disjoint Sets Problem
goal: a data structure to maintain a partition of {0, 1, . . . , n − 1} imperative data structure: module type ImperativeUnionFind = sig type t val create : int → t val find : t → int → int val union : t → int → int → unit end
S. Conchon & J.-C. Filliˆtre a
A Persistent Union-Find Data Structure
ML Workshop 2007
A Persistent Version of Tarjan’s Algorithm
representative lookup with path compression: let rec find aux a i = let ai = A.get a i in if ai == i then a, i else let a, r = find aux a ai in let a = A.set a i r in a, r the path compression made effective: let find h x = let a,rx = find aux h.link x in h.link <- a; rx
ML Workshop 2007
The Stone Soup
Sylvain Conchon and Jean-Christophe Filliˆtre a
Universit´ Paris Sud – CNRS e
S. Conchon & J.-C. Filliˆtre a
A Persistent Union-Find Data Structure
S. Conchon & J.-C. Filliˆtre a
A Persistent Union-Find Data Structure

合集下载

最优化理论与方法(南京大学)-lec1-Introduction

最优化理论与方法(南京大学)-lec1-Introduction

☆ Mathematical Programming (Optimization Problem)
• Linear Programming(线性规划) • Nonlinear Programming(非线性规划)
– Unconstrained Problems(无约束最优化方法) – Constrained Problems(约束最优化方法) ☆ Variational Inequality (VI)(变分不等式)
• Monotone VI • Non-monotone VI
5
Optimization Problem
(Mathematical) Optimization Problem
minimize f x subject to gi x bi , i 1,L ,m
g x x1,L , xn : optimization variables (优化变量)
2
Optimization Process
real world problem
analysis
validation, sensitivity analysis
algorithm, model, solution technique
numerical methods
verification 验证
computer implementation
the roads, the travel times between intersections can be considered as
constant, but if the traffic is heavy the travel times can increase
体运行时间) for handling a (long) sequence of tasks(处理一个任务序
算法导论15-16-答案.pdf

算法导论15-16-答案.pdf


j
j
w(i, j) = ∑ pl + ∑ ql
l =i
l =i −1
(5-5)
OPTIMAL-BST(p, q, n)
1 for i ← 1 to n + 1
2
do e[i, i-1] ←qi-1
3
w[i, i-1] ←qi-1
4 for l ← 1 to n
5
do for i ← 1 to n – l + 1
15-4 (5-19) Planning a company party. Professor Stewart is consulting for the president of a corporation that is planning a company party. The company has a hierarchical structure; that is, the supervisor relation forms tree rooted at the president. The personal office has ranked each employee with a conviviality rating, which is a real number. In order to make the party fun for all attendees, the president does not want both an employee and his or her immediate supervisor to attend.
To print out all the stations, call PRINT-STATIONS (l, l*, n)
启发式算法求最大团

启发式算法求最大团

启发式算法求最大团Heuristic algorithms are a type of problem-solving method that uses intuitive or experiential approaches to find approximate solutions to complex optimization problems. 启发式算法是一种问题解决方法，它使用直觉或经验性方法来寻找复杂优化问题的近似解决方案。

These algorithms are often employed when traditional optimization techniques are not efficient or feasible due to the problem's size or complexity. 这些算法通常在传统的优化技术由于问题的规模或复杂性而不够高效或可行时使用。

One common application of heuristic algorithms is in finding maximum cliques or maximum independent sets in graphs, known as the maximum clique problem. 启发式算法的一个常见应用是在图中找到最大团或最大独立集，也就是最大团问题。

The maximum clique problem is NP-complete, meaning that it is generally intractable to solve optimally for large instances using exact methods. 最大团问题是NP完全问题，意味着对于大规模实例使用精确方法解决通常是不可行的。

There are several heuristic algorithms that have been developed to tackle the maximum clique problem, each with its own strengths and weaknesses. 有几种启发式算法已经被开发用来解决最大团问题，每种算法都有其优缺点。

加权加法策略模糊目标规划法应用到质量控制系统设计(IJISA-V4-N11-2)

加权加法策略模糊目标规划法应用到质量控制系统设计(IJISA-V4-N11-2)


I.
Introduction
Even though some real-world problems can be reduced to a matter of a single objective very often it is hard to define all the aspects in terms of a single objective. Defining multiple objectives often gives a better idea of the task. Multi objective optimization has been available for about two decades, and its application in real-world problems is continuously increasing. In contrast to the plethora of techniques available for single-objective optimization, relatively few techniques have been developed for multi objective optimization , Goal programming(GP) is one of the most important methods of Multi objective optimization ,it is an extension to linear programming . the basic idea is to establish a specific numeric goal for each of the objectives, formulate an objective function for each objective, then seek a solution that minimizes Copyright © 2012 MECS