Partial Solution and Entropy

被引:0
作者
Takaoka, Tadao [1 ]
机构
[1] Univ Canterbury, Dept Comp Sci, Christchurch 1, New Zealand
来源
MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2009 | 2009年 / 5734卷
关键词
entropy; complexity; adaptive sort; minimal mergesort; ascending runs; shortest paths; nearly acyclic graphs; minimum spanning trees; SORTING ALGORITHMS; HEAPS;
D O I
暂无
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
If the given problem instance is partially solved. we want to minimize our effort to solve the problem rising that information. Ill this paper we introduce the measure of entropy H(S) for uncertainty in partially solved input data S(X) = (X(1),...,X(k)), where X is the entire data set, and each X(i) is already solved. We use the entropy measure to analyze three example problems, sorting, shortest paths and minimum spanning trees. For sorting X(i) is an ascending run, and for shortest paths, X(i) is an acyclic part in the given graph. For minimum spanning trees, X(i) is interpreted as a partially obtained minimum spanning tree for a, subgraph. The entropy measure, H(S), is defined by regarding p(i) = vertical bar X(i)vertical bar/vertical bar X vertical bar as a probability measure, that is, H(S) = -n Sigma(k)(i=1) p(i) log p(i), where n = Sigma(k)(i=1) vertical bar X(i)vertical bar. Then we show that we can sort the input data S(X) in O(H(S)) time; and solve the shortest path problem in O(m + H(S)) time where in is the number of edges of the graph. Finally we show that the minimum spanning tree is computed in O(m + H(S)) time.
引用
收藏
页码:700 / 711
页数:12
相关论文
共 11 条
[1]  
ABUAIADH D, 1994, LNCS, V834, P442
[2]  
Dijkstra E. W., 1959, NUMER MATH, V1, P269
[3]  
ESTIVILLCASTRO V, 1992, COMPUT SURV, V24, P441, DOI 10.1145/146370.146381
[4]   FIBONACCI HEAPS AND THEIR USES IN IMPROVED NETWORK OPTIMIZATION ALGORITHMS [J].
FREDMAN, ML ;
TARJAN, RE .
JOURNAL OF THE ACM, 1987, 34 (03) :596-615
[5]  
Knuth D.E., 1974, ART COMPUTER PROGRAM, V1st
[6]   MEASURES OF PRESORTEDNESS AND OPTIMAL SORTING ALGORITHMS [J].
MANNILA, H .
IEEE TRANSACTIONS ON COMPUTERS, 1985, 34 (04) :318-325
[7]  
Nakagawa Y., 2004, Transactions of the Institute of Electronics, Information and Communication Engineers A, VJ87-A, P406
[8]   Solving shortest paths efficiently on nearly acyclic directed graphs [J].
Saunders, Shane ;
Takaoka, Tadao .
THEORETICAL COMPUTER SCIENCE, 2007, 370 (1-3) :94-109
[9]   Theory of 2-3 heaps [J].
Takaoka, T .
DISCRETE APPLIED MATHEMATICS, 2003, 126 (01) :115-128
[10]  
Takaoka T, 1998, AUST COMP S, V20, P77