Movatterモバイル変換

Information and Media Technologies

Abstract

If the given problem instance is partially solved, we want to minimize our effort to solve the problem using that information. In this paper we introduce the measure of entropy,H (S), for uncertainty in partially solved input dataS (X) = (X₁, . . . ,X_k), whereX is the entire data set, and eachX_i is already solved. We propose a generic algorithm that mergesX_i's repeatedly, and finishes whenk becomes 1. We use the entropy measure to analyze three example problems, sorting, shortest paths and minimum spanning trees. For sortingX_i is an ascending run, and for minimum spanning trees,X_i is interpreted as a partially obtained minimum spanning tree for a subgraph. For shortest paths,X_i is an acyclic part in the given graph. Whenk is small, the graph can be regarded as nearly acyclic. The entropy measure,H (S), is defined by regardingp_i = ¦X_i¦/¦X¦ as a probability measure, that is,H (S) = -n (p₁ logp₁ + . . . +p_k logp_k), wheren = ¦X₁¦ + . . . + ¦X_k¦. We show that we can sort the input dataS (X) inO (H (S)) time, and that we can complete the minimum cost spanning tree inO (m +H (S)) time, wherem in the number of edges. Then we solve the shortest path problem inO (m +H (S)) time. Finally we define dual entropy on the partitioning process, whereby we give the time bounds on a generic quicksort and the shortest path problem for another kind of nearly acyclic graphs.

References (14)

Related articles (0)

Figures (0)

Supplementary material (0)

Result List ()

Cited by (0)

© 2010 Information Processing Society of Japan

Favorites & Alerts